package cn.bellychang.leetcode.question046;

import java.util.ArrayList;
import java.util.List;

/**
 *
 *
 * big question ==> smaller question
 *
 * 如果我们确定了最后一位数据，那就变成了求解剩下 n−1个数据的排列问题。
 *
 * 而最后一位数据可以是 n 个数据中的任意一个，因此它的取值就有 n 种情况。  最后一位的数据通过前(n-1)个数据交换 + 与自身交换
 *
 * 所以，“n个数据的排列”问题，就可以分解成 n 个“n−1个数据的排列”的子问题。
 *
 * @author ChangLiang
 * @date 2021/2/10
 */
public class Solution {

    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        doPermute(nums, nums.length, nums.length, res);
        return res;
    }

    private void doPermute(int[] data, int n, int k, List<List<Integer>> res) {

        // 终止条件 当k=1的时候 输出当前数组的值
        if (k == 1) {
            List<Integer> list = new ArrayList<>();
            // loop invariant:
            for (int i = 0; i < n; i++) {
                list.add(data[i]);
            }
            res.add(list);
            return;
        }

        // loop invariant: 每次变换数组最后的值 构成递推公式
        for (int i = 0; i < k; i++) {
            // 将子组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。

            // 比如[1,2,3]
            // perm(1,2,3) = perm(2,3) 1 + perm(1,3) 2 + 3 perm(1,2) 3



            // i=0 就是值1 k=3, k-1=2  将0和2交换 之后执行doPermute(k-1)

            // 内层循环
            // i=0 就是值3 k=2, k-1=1  将0和1交换 之后执行doPermute(k-1) 整体相当于执行 perm(2) 3 1
            // 之后再把0和1交换回来 3 2 1

            // i=1 就是值2 k=2, k-1=1  将1和1交换 之后执行doPermute(k-1) 整体相当于执行 perm(3) 2 1
            // 之后再把0和1交换回来 3 2 1

            // 回到外层循环 之后再把0和2交换回来 [1,2,3]  整体相当于执行 perm(3,2) 1





            // i=1 就是值2 k=3, k-1=2  将1和2交换 之后执行doPermute(k-1)
            //
            // 回到外层循环 之后再把1和2交换回来 [1,2,3]  整体相当于执行 perm(1,3) 2




            // i=2 就是值3 k=3, k-1=2  将2和2交换 之后执行doPermute(k-1)
            //
            // 回到外层循环 之后再把2和2交换回来 [1,2,3]  整体相当于执行 perm(1,2) 3

            swap(data, i, k - 1);
            doPermute(data, n, k - 1, res);
            swap(data, i, k-1);
        }

    }

    private void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

}
